package com.zsrt.ch01;

/**
 * 快速排序的核心思想：每次都必须交换1次位置  如果找到1个就不找啦 如果没有找到 继续找
 * 如果找到了就交换位置 然后不找啦
 * 如果没找到 移动指针
 * j从右向左扫描  如果找到1个 array[j]<key 就交换位置 然后就不找啦
 * 如果没有找到  j减1
 * @author scott
 *
 */
public class QuickSort {
	
	
	/**
	 * 
	 * @param array  需要打印的数组
	 */
	public static void printArray(int[] array){
		System.out.print("[");
		
		for(int index=0; index<=array.length-1;index++){
			
			if(index == array.length-1){
				System.out.print(array[index]);
			}else{
				System.out.print(array[index] +",");
			}
		}
		System.out.println("]");
	}
	
	
	/**
	 * 交换位置
	 * @param array  数组
	 * @param i      第1个元素
	 * @param j      第2个元素
	 */
	public static void changePosition(int[] array,int i ,int j){
		int temp = array[i];
		array[i]=array[j];
		array[j]=temp;
	}
	
	
	
	public static void main(String[] args) {
		
		int[] array={49,38,65,97,76,13,27};
		
		//调用快速排序的核心方法
		sort(array, 0, array.length-1);
		printArray(array);
		
	}
	
	
	/**
	 * 快速排序的核心方法
	 * @param array   要排序的数组
	 * @param begin   下标的开始位置 包括下标本身的位置
	 * @param end     下标的结束位置 包括下标本身的位置
	 */
	public static void sort(int[] array,int begin,int end){
		
		System.out.print("begin="+begin +",end="+end);
		
		int i=begin;
		int j=end;
		
		//当i=j的时候 结束整个方法
		if(i==j){
			System.out.println("结束方法 不要排序");
			return;
		}
		
		//key 关键元素
		int key=array[i];
		
		//因为不知道具体要循环多少次 所以使用死循环
		while(true){
			
			
			//1 j从后往前扫描
			while(j>i){
				//1.1 如果右边的数array[j]比关键元素key要小 需要交换位置[把i和j交换位置] 然后就不找了[break]   1.2 否则的话j-- 
				if(array[j]<key){
					//交换位置
					changePosition(array, i, j);
					break;
				}else{
					//如果右边的数array[j]比关键元素key要大 就不需要交换 j对应的指针往前移动一个位置
					j--;
				}
			}
			
			//2 i从前往后扫描
			while(j>i){
				//2.1 如果左边的数array[i]比关键元素key要大 需要交换位置[把i和j交换位置] 然后就不找了[break]   2.2 否则的话i++ 
				if(array[i]>key){
					//交换位置
					changePosition(array, i, j);
					break;
				}else{
					//如果左边的数array[i]比关键元素key要小 就不需要交换 但是i对应的指针往后移动一个位置
					i++;
				}
				
			}
			
			
			//3 如果j和i的下标相等  说明已经完成了1次循环
			if(j==i){
				//结束1趟循环
				break;
			}
		}
		printArray(array);
		//4 后面的循环和前面的循环的思路是一样的  递归
		
		//左边的子数组
		sort(array, begin, i-1);
		
		//右边的子数组
		sort(array, i+1, end);
		
	}
	
	

}
